洛谷 1099 树网的核 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1k 字 | 阅读时长 ≈ 5 分钟

第一次写这种大模拟题呢。。。觉得很考验码力和阅读理解能力，就写上了。

题意简述

给定一个带权的树，
定义：

  1. 点到路径的距离：中离最远的点的到的距离
  2. 一条路径的偏心距为：树上离路径最远的点到的距离

请找到一个路径，使得:

  1. 的所有点在这个树的直径上
  2. 中的边权和，给定
  3. 的偏心距最小

输出最小的偏心距。

思路

先说一下，这个题数据水甚，大概也是能过去的，只要顾着写就可以了，几乎不用考虑时间复杂度。

首先找到直径。然后在直径上枚举路径的两个端点，计算出这个路径的偏心距，更新答案即可。

几个细节：

  1. 偏心距就两遍更新一下
  2. 如果路径长度，那么及时，不要继续搜了（一个大优化）
  3. 适当使用以减少代码量，增加准确率（赛高！）
  4. 不要出现低级错误！！！（像我就写反了，还好我机智，要不然肝没了）

代码（与以前的题目不同，这个题目在于读代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
namespace Flandle_Scarlet
{
    #define N 11234

    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u);~i;i=G.Next(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    class Graph//存图
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<3];
            void clear()
            {
                memset(head,-1,sizeof(head));
                memset(Ed,-1,sizeof(Ed));
                EdgeCount=0;
            }

            void AddEdge(int u,int v,int w=1)
            {
                ++EdgeCount;
                Ed[EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1)
            {
                AddEdge(u,v,w);AddEdge(v,u,w);
            }

            int Start(int u)
            {
                return head[u];
            }
            int To(int u)
            {
                return Ed[u].To;
            }
            int Label(int u)
            {
                return Ed[u].Label;
            }
            int Next(int u)
            {
                return Ed[u].Next;
            }

    }G;
    int n,s;
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        G.clear();
        R1(n),R1(s);
        F(i,1,n-1)
        {
            int u,v,w;
            R1(u),R1(v),R1(w);
            G.Add2(u,v,w);
        }
    }

    int dis[N],fa[N];
    void DFS(int u,int f)//非常普通的DFS
    {
        if (u==f) dis[u]=0,fa[u]=-1;
        else fa[u]=f;

        Tra(i,u)
        {
            int v=G.To(i);
            if (v!=f)
            {
                dis[v]=dis[u]+G.Label(i);
                DFS(v,u);
            }
        }
    }
    int dis2[N];//注意：这个要新开一个dis数组用，因为上面那个dis数组要用来判断路径长度是否<=S
    bool In[N];
    void DFS2(int u,int f)
    {
        Tra(i,u)
        {
            int v=G.To(i);
            if (!In[v] and v!=f)//注意：判断!In[v]是为了只考虑路径外面的点
            {
                dis2[v]=dis2[u]+G.Label(i);
                DFS2(v,u);
            }
        }
    }
    void Soviet()
    {
        int l,r;//直径的两端
        DFS(1,1);
        l=max_element(dis+1,dis+n+1)-dis;//max_element:返回区间内最大值出现的第一个位置
//      min_element同理，返回区间内最小值出现的第一个位置
        DFS(l,l);
        r=max_element(dis+1,dis+n+1)-dis;
//        printf("diameter: %d %d\n",l,r);
//      直径的求法：从1开始找到最远的点，就是第一个端点。再从这个端点跑到最远的点，就是第二个端点。
        int ans=0x3f3f3f3f;
        for(int i=r;~i;i=fa[i])
        {
            for(int j=i;~j;j=fa[j])//枚举路径上的两个点
            {
                if (dis[i]-dis[j]<=s)//注意，此处的dis是以r为根的意义下算的，但是fa数组是以
//              l为根的意义下算的，所以j是在i的下面的，而不是上面，所以我这里i和j写反了，大家千万不要再犯这个错误了T_T
                {
//                    printf("i=%d j=%d\n",i,j);
                    FK(In);
                    for(int k=i;k!=j;k=fa[k])
                    {
                        In[k]=1;
                    }
                    In[j]=1;//标记路径上的点

                    for(int k=i;k!=j;k=fa[k])
                    {
                        dis2[k]=0;
                        DFS2(k,k);
                    }
                    dis2[j]=0;DFS2(j,j);//更新最小距离

                    ans=min(ans,*max_element(dis2+1,dis2+n+1));
                    //更新答案
                }
                else break;//注意及时break
            }
        }
        printf("%d\n",ans);
    }
    #define FlandreScarlet void
    FlandreScarlet IsMyWife()
    {
        if (0)
        {
            freopen("","r",stdin);
            freopen("","w",stdout);
        }
        Input();
        Soviet();
    }
};
int main()
{
    Flandle_Scarlet::IsMyWife();
    return 0;
}
w